Resource for Source: C/C++/Resource for Source - C-C++.iso/codelib9/v_11_11/allison/bits.c

C/C++ Source or Header | 1995-11-01 | 4.9 KB | 262 lines

LISTING 7 - Bits Object Implementation
/* bits.c */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <assert.h>
#include "bits.h"

/* Pick the base integral type */
typedef unsigned char Block;

/* Some implementation specifics */
#define BLKSIZ          (CHAR_BIT * sizeof(Block))
#define offset(b)       (b % BLKSIZ)
#define mask1(b)        ((Block)1 << offset(b))
#define mask0(b)       ~((Block)1 << offset(b))

/* Data Structure */
typedef struct bits
{
    size_t nbits_;      /* The # of bits */
    Block *bits_;       /* The base array */
    size_t nblks_;      /* The # of blocks in base array */
    Block clean_mask_;  /* To mask-off unused bits */
} Bits;

/* Private functions */
static size_t word_(Bits* bp, size_t bit)
{
    return bp->nblks_ - 1 - bit/BLKSIZ;
}

static void set_(Bits *bp, size_t b)
{
    bp->bits_[word_(bp,b)] |= mask1(b);
}

static void reset_(Bits *bp, size_t b)
{
    bp->bits_[word_(bp,b)] &= mask0(b);
}

static void toggle_(Bits *bp, size_t b)
{
    bp->bits_[word_(bp,b)] ^= mask1(b);
}

static int test_(Bits *bp,size_t b)
{
    return !!(bp->bits_[word_(bp,b)] & mask1(b));
}

static size_t count_block_(Block n)
{
    size_t sum = 0;

    while (n)
    {
        if (n & (Block)1)
            ++sum;
        n >>= 1;
    }
    return sum;
}

static void cleanup_(Bits *bp)
{
    if (bp->nbits_ % BLKSIZ)
        bp->bits_[0] &= bp->clean_mask_;
}

/* Implementation of public interface */
Bits * bits_create(size_t nbits)
{
    Bits *bp = malloc(sizeof(Bits));
    size_t nbytes;

    if (bp == NULL)
        return NULL;

    /* Allocate base array */
    bp->nblks_ = (nbits + BLKSIZ - 1) / BLKSIZ;
    nbytes = bp->nblks_ * sizeof(Block);
    bp->bits_ = malloc(nbytes);
    if (bp->bits_ == NULL)
    {
        free(bp);
        return NULL;
    }

    memset(bp->bits_,'\0',nbytes);
    bp->nbits_ = nbits;
    bp->clean_mask_ = ~(Block)0 >> (bp->nblks_*BLKSIZ - nbits);
    return bp;
}

unsigned bits_to_uint(Bits *bp)
{
    size_t nblks = sizeof(unsigned) / sizeof(Block);
    if (nblks > 1)
    {
        int i;
        unsigned n = bp->bits_[bp->nblks_ - nblks];

        /* Collect low-order sub-blocks into an unsigned */
        if (nblks > bp->nblks_)
            nblks = bp->nblks_;
        while (--nblks)
            n = (n << BLKSIZ) | bp->bits_[bp->nblks_ - nblks];
        return n;
    }
    else
        return (unsigned) bp->bits_[bp->nblks_ - 1];
}

Bits * bits_from_uint(Bits *bp, unsigned n)
{
    size_t nblks = sizeof(unsigned) / sizeof(Block);
    assert(bp);
    memset(bp->bits_, '\0', bp->nblks_ * sizeof(Block));
    if (nblks > 1)
    {
        int i;
        if (nblks > bp->nblks_)
            nblks = bp->nblks_;
        for (i = 1; i <= nblks; ++i)
        {
            bp->bits_[bp->nblks_ - i] = (Block) n;
            n >>= BLKSIZ;
        }
    }
    else
        bp->bits_[bp->nblks_ - 1] = n;

    return bp;
}

Bits * bits_set(Bits *bp, size_t bit)
{
    assert(bp && (bit < bp->nbits_));
    set_(bp,bit);
    return bp;
}

Bits * bits_set_all(Bits *bp)
{
    assert(bp);
    memset(bp->bits_,~0u,bp->nblks_*sizeof(Block));
    cleanup_(bp);
    return bp;
}

Bits * bits_reset(Bits *bp, size_t bit)
{
    assert(bp && (bit < bp->nbits_));
    reset_(bp,bit);
    return bp;
}

Bits * bits_reset_all(Bits *bp)
{
    assert(bp);
    memset(bp->bits_,'\0',bp->nblks_*sizeof(Block));
    return bp;
}

Bits * bits_toggle(Bits *bp, size_t bit)
{
    assert(bp && (bit < bp->nbits_));
    toggle_(bp,bit);
    return bp;
}

Bits * bits_toggle_all(Bits *bp)
{
    size_t nw;

    assert(bp);
    nw = bp->nblks_;
    while (nw--)
        bp->bits_[nw] = ~bp->bits_[nw];
    cleanup_(bp);
    return bp;
}

int bits_test(Bits *bp,size_t bit)
{
    assert(bp && (bit < bp->nbits_));
    return test_(bp,bit);
}

int bits_any(Bits *bp)
{
    int i;

    assert(bp);
    for (i = 0; i < bp->nblks_; ++i)
        if (bp->bits_[i])
            return 1;
    return 0;
}

size_t bits_count(Bits *bp)
{
    int i;
    size_t sum;

    assert(bp);
    for (i = 0, sum = 0; i < bp->nblks_; ++i)
        sum += count_block_(bp->bits_[i]);
    return sum;
}

Bits * bits_put(Bits *bp, FILE *f)
{
    int i;

    assert(bp);
    for (i = 0; i < bp->nbits_; ++i)
        fprintf(f,"%d",bits_test(bp,bp->nbits_-1-i));
    return bp;
}

Bits * bits_get(Bits *bp, FILE *f)
{
    char *buf;
    char format[9];

    /* Reset all bits */
    assert(bp);
    bits_reset_all(bp);

    /* Allocate string buffer */
    buf = malloc(bp->nbits_+1);
    if (buf == NULL)
        return 0;

    /* Build read format (e.g., " %16[01]") */
    sprintf(format," %%%d[01]",bp->nbits_);
    if (fscanf(f,format,buf) == 1)
    {
        int i;
        size_t slen = strlen(buf);

        /* Set corresponding bits in bitset */
        for (i = 0; i < slen; ++i)
            if (buf[slen-1-i] == '1')
                bits_set(bp,i);
    }
    free(buf);
    return bp;
}

void bits_destroy(Bits *bp)
{
    assert(bp);
    free(bp->bits_);
    free(bp);
}